#include <bits/stdc++.h>

using namespace std;

// 柱状图中最大的矩形
// 给定 n 个非负整数，用来表示柱状图中各个柱子的高度
// 每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积
// 测试链接：https://leetcode.cn/problems/largest-rectangle-in-histogram

class Solution 
{
private:
    static const int MAXN = 100001;
    int st[MAXN];
    int r;

public:
    int largestRectangleArea(vector<int>& heights) 
    {
        int n = heights.size(), ans = 0, cur, left;
        for(int i = 0; i < n; ++i)
        {
            while(r > 0 && heights[st[r - 1]] >= heights[i])
            {
                cur = st[--r];
                left = r > 0 ? st[r - 1] : -1;
                ans = max(ans, (i - left - 1) * heights[cur]);
            }
            st[r++] = i;
        }
        while(r > 0)
        {
            cur = st[--r];
            left = r > 0 ? st[r - 1] : -1;
            ans = max(ans, (n - left - 1) * heights[cur]);
        }
        return ans;
    }
};


class Solution 
{
public:
    int largestRectangleArea(vector<int>& heights) 
    {
        int n = heights.size();
        vector<int> left(n), right(n, n);

        stack<int> st;
        for(int i = 0; i < n; ++i)
        {
            while(!st.empty() && heights[st.top()] >= heights[i]) 
            {
                right[st.top()] = i;
                st.pop();
            }
            left[i] = st.empty() ? -1 : st.top();
            st.push(i);
        }


        int ret = 0;
        for(int i = 0; i < n; ++i)
        {
            ret = max(ret, (right[i] - left[i] - 1) * heights[i]);
        }
        return ret;
    }
};